In [1]:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
In [2]:
import networkx as nx
In [3]:
nodes = list(range(1, 8))
edges = [(i, j) for i in nodes for j in nodes[i:]]
In [4]:
g = nx.Graph()
g.add_edges_from(edges)
In [5]:
(1, 2) in g.edges
Out[5]:
In [6]:
def check_completeness(graph):
for node1 in graph.nodes:
for node2 in graph.nodes:
if node1 != node2 and (node1, node2) not in graph.edges:
return 'not complete'
return 'complete'
In [7]:
h = nx.Graph()
h.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1)])
In [8]:
check_completeness(h)
Out[8]:
In [9]:
check_completeness(g)
Out[9]:
In [10]:
g = nx.complete_graph(7)
g.edges
Out[10]:
In [11]:
check_completeness(g)
Out[11]:
In [12]:
def draw_with_labels(graph, layout_type=None, **kwargs):
plt.figure(figsize=(16, 10))
if layout_type == None:
nx.draw(graph, with_labels=True)
elif layout_type == 'circular':
nx.draw_circular(graph, with_labels=True)
elif layout_type == 'random':
nx.draw_random(graph, with_labels=True)
elif layout_type == 'spectral':
nx.draw_spectral(graph, with_labels=True)
elif layout_type == 'shell':
nx.draw_shell(graph, with_labels=True, **kwargs)
In [13]:
draw_with_labels(g, 'circular')
In [14]:
draw_with_labels(g, 'shell', nlist=[range(4, 7), range(4)])
In [15]:
h1 = nx.cycle_graph(4)
h2 = nx.complete_graph(range(4, 7))
h3 = nx.complete_bipartite_graph([7, 8], [9])
h = nx.Graph()
h.add_edges_from(h1.edges)
h.add_edges_from(h2.edges)
h.add_edges_from(h3.edges)
In [16]:
draw_with_labels(h)
In [17]:
d = nx.DiGraph()
d.add_nodes_from(range(4))
d.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (3, 1), (0, 2), (1, 0)])
nx.diameter(d)
Out[17]:
In [18]:
draw_with_labels(d, 'circular')
In [19]:
d = nx.DiGraph()
d.add_nodes_from(range(4))
d.add_weighted_edges_from([(0, 1, 0.5), (1, 2, 0.2),
(2, 3, 0.1), (0, 2, 0.65), (1, 0, 0.9)])
draw_with_labels(d, 'circular')
nx.draw_networkx_edge_labels(d, pos=nx.circular_layout(d),
edge_labels={item[0]:item[1]['weight'] for item in d.edges.items()});
In [20]:
edgelist = nx.read_gpickle('edges_1.pkl')
g1 = nx.Graph()
g1.add_edges_from(edgelist)
g1.nodes
Out[20]:
In [21]:
draw_with_labels(g1)
In [22]:
adj = np.zeros([12, 12], dtype=int)
for edge in g1.edges:
adj[edge[0], edge[1]] = 1
adj[edge[1], edge[0]] = 1
adj
Out[22]:
In [23]:
nx.adj_matrix(g1).todense()
Out[23]:
In [24]:
dist = np.zeros([12, 12], dtype=int)
sp = nx.all_pairs_shortest_path_length(g1)
for item in sp:
for key in item[1]:
dist[item[0], key] = item[1][key]
In [25]:
dist
Out[25]:
A cutpoint (whatever this means mathematically, I thing nothing though, it should be a cut set) could be the edge between 5 and 6:
In [26]:
cut = [(5, 6)]
g1.remove_edges_from(cut)
draw_with_labels(g1)
In [27]:
edgelist = nx.read_gpickle('edges_2.pkl')
g2 = nx.Graph()
g2.add_edges_from(edgelist)
g2.nodes
Out[27]:
In [28]:
draw_with_labels(g2)
In [29]:
# clique = subgraph such that every two nodes are adjacent (i.e. it is a complete graph if considered by itself)
# maximal clique = a clique which isn't contained in any other clique
for mc in nx.find_cliques(g2):
print(mc)
In [30]:
# degree = number of adjacent nodes
g2.degree
Out[30]:
In [31]:
# closeness centrality or closeness = reciprocal of the sum of the lengths of the shortest paths between
# the node and all other nodes divided by N-1 - the greater the more central
nx.closeness_centrality(g2)
Out[31]:
In [32]:
# betweenness centrality or betweenness = sum of the number of shortest paths from all nodes different from v that
# pass through v divided by the number of shortest paths from all nodes different from v
nx.betweenness_centrality(g2)
Out[32]:
Actors 0, 1 and 2 have the greatest control: they are more and more easily connected to others and, most of all, the betweenness tells us that most of the shortest paths from one person to another go through them.
Some actors have betweenness measures of 0 because no shortest path needs them: this may be because they have a low number of connection that are already connected to others, i.e. they are peripheral nodes of the graph and they don't know someone which isn't known by someone else.
In [33]:
g2_copy = g2.copy()
g2_copy.remove_node(0)
g2_copy.add_edge(10, 14)
g2_copy.remove_edge(1, 2)
draw_with_labels(g2_copy)
In [34]:
# eccentricity = greatest geodesic distance between v and any other node
nx.eccentricity(g2_copy, 1)
Out[34]:
In [36]:
# for mc in nx.find_cliques(g2_copy):
# if 1 in mc:
# print(mc)
nx.cliques_containing_node(g2_copy, 1)
Out[36]:
In [37]:
# density = how much the number of edges is close to the maximum possible (complete graph)
nx.density(g2_copy)
Out[37]:
In [38]:
g2_copy.remove_node(1)
nx.density(g2_copy)
Out[38]:
In [244]:
edgelist = nx.read_gpickle('edges_3.pkl')
g3 = nx.DiGraph()
g3.add_edges_from(edgelist)
g3.nodes
Out[244]:
In [229]:
draw_with_labels(g3)
In [247]:
# create the adjacency matrix
adj = nx.adjacency_matrix(g3)
adj = adj.todense()
# node 1 comes before node 0
adj
Out[247]:
In [270]:
# in-out degree centrality = fraction of number of nodes incoming-outcoming edges are connected to
n_edges = len(g3.edges)
insum = np.sum(adj, axis=0).tolist()[0]
outsum = np.sum(adj, axis=1).reshape(1, -1).tolist()[0]
# remember that node 1 comes before node 0
insum[0], insum[1] = insum[1], insum[0]
outsum[0], outsum[1] = outsum[1], outsum[0]
In [271]:
[d / n_edges for d in insum]
Out[271]:
In [272]:
[d / n_edges for d in outsum]
Out[272]:
In [223]:
# compare your results to the in and out_degree_centrality methods
nx.in_degree_centrality(g3)
Out[223]:
In [224]:
nx.out_degree_centrality(g3)
Out[224]: